1. Field of the Invention
The present invention relates to a Reed-Solomon error-correcting circuit that is used as a system of error correction, and also to the Euclidian algorithm and apparatus that are used in systems of error correction such as BHC error-correcting systems and Reed-Solomon error correcting systems.
2. Description of the Related Art
Error correcting systems such as BHC error-correcting systems and Reed-Solomon error-correcting systems are used as error correcting systems in various fields such as recording media like optical fibers and digital transmission systems like digital satellite broadcasting systems. Of recent years, as the scale of recording and transmission has become greater, error-correcting circuits that accommodate high-speed processing have been developed.
So far, as a Reed-Solomon error-correcting circuit that accommodates high-speed processing, there has been known the one disclosed in Japanese Patent Laid-Open Publication No. 3-195216.
This Reed-Solomon error-correcting circuit comprises, as shown in FIG. 18, a syndrome generating circuit 1 (equivalent to the syndrome generating circuit in the Reed-Solomon error-correction circuit of the present invention), an error-locator-polynomial deriving circuit 2 (equivalent to the error-locator-polynomial/error-evaluator-polynomial calculating circuit within the error correcting circuit in the Reed-Solomon error-correcting circuit of the present invention), an error-location detecting circuit 3 and an error-pattern detecting circuit 4 and an AND gate 5 and an EXOR gate 6 (equivalent to the correcting circuit within the error correcting circuit in the Reed-Solomon error-correcting circuit of the present invention), and a delay circuit 7 (equivalent to the memory in the Reed-Solomon error-correcting circuit of the present invention).
The error-locator-polynomial deriving circuit in this Reed-Solomon error-correcting circuit requires, as described in the embodiment of the patent disclosure, a great number of Galois-field calculating circuits installed between the registers of the shift registers, in order to accommodate high-speed processing. Therefore, there is a problem that the scale of hardware is large.
Also, in order to limit internal delays and increases in power consumption due to large-scale hardware, a high-speed clock is not used, and a received symbol clock is used for operation. Therefore, one packet of time is taken for processing in the error-locator-polynomial deriving circuit.
Therefore, there is required, at least, parallel operation with three-step pipelined processing by the syndrome generating circuit, the error-locator-polynomial deriving circuit, and the error-location detecting circuit, error-pattern detecting circuit, AND gate, and EXOR gate. Therefore, the delay circuit must hold three packets of data, so that the scale of hardware becomes still larger.
Next, the operation of the above circuit is described. In error correcting systems such as BHC error-correcting systems and Reed-Solomon error-correcting systems, first a syndrome equation S(z)=skxe2x88x921zkxe2x88x921+skxe2x88x922zkxe2x88x922+ . . . +s0 based on the received signal is obtained on the receiver side. In the Reed-Solomon error-correcting circuit described above, the syndrome generating circuit performs this operation.
If there exists no error in the signal, then the coefficients Skxe2x88x921 to s0 of the syndrome equation S(z) become skxe2x88x921=skxe2x88x922= . . . =s0=0, that is, the syndrome equation becomes S(z)=0. If there exist some errors in the signal, the syndrome equation becomes S(z)xe2x89xa00.
If there exist some errors in the received signal, so that the syndrome signal becomes S(z)xe2x89xa00, then, the error-locator-polynomial "sgr"(z) is obtained from the syndrome equation S(z). In the Reed-Solomon error-correcting circuit described above, the error-locator-polynomial deriving circuit performs this operation.
Finally, errors are corrected by using the error-locator-polynomial "sgr"(z).
Generally, in order to obtain the error-locator-polynomial "sgr"(z) from the syndrome equation S(z), an Euclid""s algorithm is used. In the past, as the Euclid""s algorithm, the one described in xe2x80x9cDevelopment of Error correcting methods and LSI for optical disk drives,xe2x80x9d Computer Architecture, 67-3 (Sep. 16, 1987) is known.
A description is given in the following with the Reed-Solomon error-correcting method based on a report of the Committee on Digital Broadcasting Systems in the Council of Electronic Communication.
Code generating polynomial:
g(z)=(z+xcex10)(z+xcex11)(z+xcex12) . . . (z+xcex115), (xcex1=02h).
Field generating polynomial: x8+x4+x3+x2+1.
Packet length: 204 bytes.
Information bytes therein: 188 bytes.
Error correcting number: 8 bytes.
In the Euclid""s algorithm of the Reed-Solomon error-correcting system described above, initial setting for the polynomials A(z), B(z), L(z), and M(z) is made from the syndrome equation
S(z)=s15z15+s14Z14+ . . . +s0
based on the signal decoded with the Reed-Solomon code, where s15, . . . , s0 are elements of the Galois field GF(28) . Then the error-locator-polynomial "sgr"(z) is obtained through Galdis-field operations. Operations on Galois fields are described in Hideki Imai, Coding Theory, Chapter 3, Institute of Electronics and Communication Engineers of Japan.
In the following is described the Euclid""s algorithm in a prior example in conjunction with figures.
FIG. 19 is a flowchart illustrating the method of initial setting in a prior exemplary Euclid""s algorithm. FIG. 20 is a flowchart illustrating a general Euclid""s algorithm after initial setting.
In the Euclid""s algorithm in the prior example, according to the method of initial setting illustrated in FIG. 19, initial setting for the polynomials A(z), B(z), L(z), and M(z) is performed from the syndrome equation
S(z)=s15z15+s14Z14+ . . . +s0
based on a signal decoded with the Reed-Solomon error correcting code, where s15, . . , s0 are elements of the Galois field GF(28). Then, according to the general Euclid algorithm after the initial setting illustrated in FIG. 20, Galois-field operations are performed to obtain the error-locator-polynomial "sgr"(z). In the Galois-field operations, processing for reducing the degrees of the polynomials A(z) and B(z) is performed. When at least one of the degrees of the polynomials A(z) and B(z) becomes equal to or less than 7, the processing is terminated.
In the following is described an example of the Euclid""s algorithm in the prior example illustrated in FIGS. 19, 20.
In the following, a first example of operations in the Euclid""s algorithm in the prior example is described. This example of operations is in the case where s15, . . , s8xe2x89xa00 for the coefficients of the syndrome equation S(z). In this example of operations, after sixth operations on the Galois field, the error-locator-polynomial "sgr"(z) is obtained.
First example of operations in prior Euclidean algorithm. Syndrome.
S(z)=85z15+EBz14+E9z13+A9z12+F8z11+AEz10+C4z9+14z8+A7z7+72z6+A0z5+58z4+91z3+51z2+5Fz+FF
After initial setting.                               A          ⁡                      (            z            )                          =                  z          16                                                  B          ⁡                      (            z            )                          =                              85            ⁢                          z              15                                +                      EBz            14                    +                      E9z            13                    +                      A9z            12                    +                      F8z            11                    +                      AEz            10                    +                      C4z            9                    +                      14            ⁢                          z              8                                +                      A7z            7                    +                      72            ⁢                          z              6                                +                      A0z            5                    +                      58            ⁢                          z              4                                +                      91            ⁢                          z              3                                +                      51            ⁢                          z              2                                +                      5            ⁢            Fz                    +          FF                                                  L          ⁡                      (            Z            )                          =                                                                               ⁢          0                                                  M          ⁡                      (            Z            )                          =                                                                              ⁢          1                    
After first Galois-field operations.                               A          ⁡                      (            z            )                          =                              EBz            15                    +                      E9z            14                    +                      A9z            13                    +                      F8z            12                    +                      AEz            11                    +                      C4z            10                    +                      14            ⁢                          z              9                                +                      A7z            8                    +                      72            ⁢                          z              7                                +                      A0z            6                    +                      58            ⁢                          z              5                                +                      91            ⁢                          z              4                                +                      51            ⁢                          z              3                                +                      5            ⁢                          Fz              2                                +          FFz                                                  B          ⁡                      (            z            )                          =                              85            ⁢                          z              15                                +                      EBz            14                    +                      E9z            13                    +                      A9z            12                    +                      F8z            11                    +                      AEz            10                    +                      C4z            9                    +                      14            ⁢                          z              8                                +                      A7z            7                    +                      72            ⁢                          z              6                                +                      A0z            5                    +                      58            ⁢                          z              4                                +                      91            ⁢                          z              3                                +                      51            ⁢                          z              2                                +                      5            ⁢            Fz                    +          FF                                                  L          ⁡                      (            Z            )                          =                                                                           ⁢          z                                                  M          ⁡                      (            Z            )                          =                                                                              ⁢          1                    
After second Galois-field operations.                               A          ⁡                      (            z            )                          =                                                                                ⁢            96            ⁢                          z              14                                +                      6            ⁢                          z              13                                +                      48            ⁢                          z              12                                +                      A7z            11                    +                      71            ⁢                          z              10                                +                      88            ⁢                          z              9                                +                      D4z            8                    +                      C8z            7                    +                      20            ⁢                          z              6                                +                      E7z            5                    +                      27            ⁢                          z              4                                +                      C9z            3                    +                      E6z            2                    +                      4            ⁢            Cz                    +          C                                                  B          ⁡                      (            z            )                          =                              85            ⁢                          z              15                                +                      EBz            14                    +                      E9z            13                    +                      A9z            12                    +                      F8z            11                    +                      AEz            10                    +                      C4z            9                    +                      14            ⁢                          z              8                                +                      A7z            7                    +                      72            ⁢                          z              6                                +                      A0z            5                    +                      58            ⁢                          z              4                                +                      91            ⁢                          z              3                                +                      51            ⁢                          z              2                                +                      5            ⁢            Fz                    +          FF                                                  L          ⁡                      (            Z            )                          =                                                                                             ⁢            z                    +          68                                                  M          ⁡                      (            Z            )                          =                                                                              ⁢          1                    
After third Galois-field operations.                               A          ⁡                      (            z            )                          =                              96            ⁢                          z              14                                +                      06            ⁢                          z              13                                +                      48            ⁢                          z              12                                +                      A7z            11                    +                      71            ⁢                          z              10                                +                      88            ⁢                          z              9                                +                      D4z            8                    +                      C8z            7                    +                      20            ⁢                          z              6                                +                      E7z            5                    +                      27            ⁢                          z              4                                +                      C9z            3                    +                      E6z            2                    +                      4            ⁢            Cz                    +                      0            ⁢            C                                                            B          ⁡                      (            z            )                          =                              91            ⁢                          z              14                                +                      18            ⁢                          z              13                                +                      3            ⁢                          Bz              12                                +                      4            ⁢                          Dz              11                                +                      A4z            10                    +                      3            ⁢                          Ez              9                                +                      BCz            8                    +                      F6z            7                    +                      42            ⁢                          z              6                                +                      6            ⁢                          Bz              5                                +                      10            ⁢                          z              4                                +                      41            ⁢                          z              3                                +                      7            ⁢                          z              2                                +          ABz          +          FF                                                  L          ⁡                      (            Z            )                          =                                                                                ⁢            z                    +          68                                                  M          ⁡                      (            Z            )                          =                              E0z            2                    +          A0z          +          1                    
After fourth Galois-field operations.                               A          ⁡                      (            z            )                          =                                                                               ⁢            71            ⁢                          z              13                                +                      E1z            12                    +                      41            ⁢                          z              11                                +                      B7z            10                    +                      9            ⁢                          Fz              9                                +                      65            ⁢                          z              8                                +                      6            ⁢                          Dz              7                                +                      19            ⁢                          z              6                                +                      61            ⁢                          z              5                                +                      7            ⁢                          Dz              4                                +                      9            ⁢                          Az              3                                +                      14            ⁢                          z              2                                +                      55            ⁢            z                    +          A2                                                  B          ⁡                      (            z            )                          =                              91            ⁢                          z              14                                +                      18            ⁢                          z              13                                +                      3            ⁢                          Bz              12                                +                      4            ⁢                          Dz              11                                +                      A4z            10                    +                      3            ⁢                          Ez              9                                +                      BCz            8                    +                      F6z            7                    +                      42            ⁢                          z              6                                +                      6            ⁢                          Bz              5                                +                      10            ⁢                          z              4                                +                      41            ⁢                          z              3                                +                      7            ⁢                          z              2                                +          ABz          +          FF                                                  L          ⁡                      (            Z            )                          =                              2            ⁢                          Bz              2                                +                      5            ⁢            Fz                    +                      4            ⁢            E                                                            M          ⁡                      (            Z            )                          =                              E0z            2                    +          A0z          +          1                    
After fifth Galois-field operations.                               A          ⁡                      (            z            )                          =                                                                                           ⁢            71            ⁢                          z              13                                +                      E1z            12                    +                      41            ⁢                          z              11                                +                      B7z            10                    +                      9            ⁢                          Fz              9                                +                      65            ⁢                          z              8                                +                      6            ⁢                          Dz              7                                +                      19            ⁢                          z              6                                +                      61            ⁢                          z              5                                +                      7            ⁢                          Dz              4                                +                      9            ⁢                          Az              3                                +                      14            ⁢                          z              2                                +                      55            ⁢            z                    +          A2                                                  B          ⁡                      (            z            )                          =                                                                                           ⁢                          FEz              13                                +                      EBz            12                    +                      37            ⁢                          z              11                                +                      49            ⁢                          z              10                                +                      6            ⁢                          Az              9                                +                      61            ⁢                          z              8                                +                      CCz            7                    +                      DCz            6                    +                      B9z            5                    +                      8            ⁢                          Bz              4                                +                      84            ⁢                          z              3                                +                      42            ⁢                          z              2                                +          A8z          +          FF                                                  L          ⁡                      (            Z            )                          =                                                                                ⁢            2            ⁢                          Bz              2                                +                      5            ⁢            Fz                    +                      4            ⁢            E                                                            M          ⁡                      (            Z            )                          =                              4            ⁢                          Ez              3                                +                      49            ⁢                          z              2                                +          BAz          +          1                    
After sixth Galois-field operations.                               A          ⁡                      (            z            )                          =                                                                                                                                                                                                                                     ⁢            59            ⁢                          z              2                        ⁢                                                                 +          93                                                  B          ⁡                      (            z            )                          =                                                                                           ⁢                          FEz              13                                +                      EBz            12                    +                      37            ⁢                          z              11                                +                      49            ⁢                          z              10                                +                      6            ⁢                          Az              9                                +                      61            ⁢                          z              8                                +                      CCz            7                    +                      DCz            6                    +                      B9z            5                    +                      8            ⁢                          Bz              4                                +                      84            ⁢                          z              3                                +                      42            ⁢                          z              2                                +          A8z          +          FF                                                  L          ⁡                      (            Z            )                          =                  xe2x80x83                ⁢                              6            ⁢                          Az              3                                +                      9            ⁢                          Cz              2                                +          FEz          +          E                                                  M          ⁡                      (            Z            )                          =                              4            ⁢                          Ez              3                                +                      49            ⁢                          z              2                                +          BAz          +          1                    
Result.
"sgr"(z)=L(Z)=6Az3+9Cz2FEz+E
In the following, a second example of operations in the Euclid""s algorithm in the prior example is described. This example of operations is in the case where s15xe2x89xa00 and at least one of s14, . . , s8 is 0 for the coefficients of the syndrome equation S(z). In this example of operations, after fourth operations on the Galois field, the error-locator-polynomial "sgr"(z) is obtained.
Second example of operations in prior Euclidean algorithm. Syndrome.       S    ⁡          (      z      )        =            9      ⁢              Fz        15            ⁢                                               +          94      ⁢              z        12              +          F4z      11        +          ECz      10        +          6      ⁢              Dz        9              +          5      ⁢              Fz        8              +          27      ⁢              z        7              +          5      ⁢              Cz        6              +          96      ⁢              z        5              +          21      ⁢              z        4              +          A0z      3        +          BFz      2        +          7      ⁢      Fz        +    46  
After initial setting                               A          ⁡                      (            z            )                          =                  z          16                                                  B          ⁡                      (            z            )                          =                              9            ⁢                          Fz              15                        ⁢                                                                             +                      94            ⁢                          z              12                                +                      F4z            11                    +                      ECz            10                    +                      6            ⁢                          Dz              9                                +                      5            ⁢                          Fz              8                                +                      27            ⁢                          z              7                                +                      5            ⁢                          Cz              6                                +                      96            ⁢                          z              5                                +                      21            ⁢                          z              4                                +                      A0z            3                    +                      BFz            2                    +                      7            ⁢            Fz                    +          46                                                  L          ⁡                      (            Z            )                          =                                                                               ⁢          0                                                  M          ⁡                      (            Z            )                          =                                                                              ⁢          1                    
After first Galois-field operations                               A          ⁡                      (            z            )                          =                                                                     +                      94            ⁢                          z              13                                +                      F4z            12                    +                      ECz            11                    +                      6            ⁢                          Dz              10                                +                      5            ⁢                          Fz              9                                +                      27            ⁢                          z              8                                +                      5            ⁢                          Cz              7                                +                      96            ⁢                          z              6                                +                      21            ⁢                          z              5                                +                      A0z            4                    +                      BFz            3                    +                      7            ⁢                          Fz              2                                +                      46            ⁢            z                                                            B          ⁡                      (            z            )                          =                              9            ⁢                          Fz              15                        ⁢                                                                             +                      94            ⁢                          z              12                                +                      F4z            11                    +                      ECz            10                    +                      6            ⁢                          Dz              9                                +                      5            ⁢                          Fz              8                                +                      27            ⁢                          z              7                                +                      5            ⁢                          Cz              6                                +                      96            ⁢                          z              5                                +                      21            ⁢                          z              4                                +                      A0z            3                    +                      BFz            2                    +                      7            ⁢            Fz                    +          46                                                  L          ⁡                      (            Z            )                          =                                                                           ⁢          z                                                  M          ⁡                      (            Z            )                          =                                                                              ⁢          1                    
After second Galois-field operations                               A          ⁡                      (            z            )                          =                                                                                          ⁢            94            ⁢                          z              13                                +                      F4z            12                    +                      ECz            11                    +                      6            ⁢                          Dz              10                                +                      5            ⁢                          Fz              9                                +                      27            ⁢                          z              8                                +                      5            ⁢                          Cz              7                                +                      96            ⁢                          z              6                                +                      21            ⁢                          z              5                                +                      A0z            4                    +                      BFz            3                    +                      7            ⁢                          Fz              2                                +                      46            ⁢            z                                                            B          ⁡                      (            z            )                          =                                                                              ⁢                          Bz              14                                +                      2            ⁢                          Ez              13                                +                      81            ⁢                          z              12                                +                      91            ⁢                          z              11                                +                      38            ⁢                          z              10                                +                      2            ⁢                          Fz              9                                +                      FAz            8                    +                      BDz            7                    +                      FDz            6                    +                      41            ⁢                          z              5                                +                      C3z            4                    +                      FDz            3                    +                      BFz            2                    +                      7            ⁢            Fz                    +          46                                                  L          ⁡                      (            Z            )                          =                                                                           ⁢          z                                                  M          ⁡                      (            Z            )                          =                              1            ⁢                          Dz              3                        ⁢                                                                              +          1                    
After third Galois-field operations                               A          ⁡                      (            z            )                          =                                                                                          ⁢            94            ⁢                          z              13                                +                      F4z            12                    +                      ECz            11                    +                      6            ⁢                          Dz              10                                +                      5            ⁢                          Fz              9                                +                      27            ⁢                          z              8                                +                      5            ⁢                          Cz              7                                +                      96            ⁢                          z              6                                +                      21            ⁢                          z              5                                +                      A0z            4                    +                      BFz            3                    +                      7            ⁢                          Fz              2                                +                      46            ⁢            z                                                            B          ⁡                      (            z            )                          =                                                                                          ⁢                          D1z              13                                +                      43            ⁢                          z              12                                +                      E9z            11                    +                      2            ⁢                          z              10                                +                      DCz            9                    +                      E4z            8                    +                      8            ⁢                          Ez              7                                +                      46            ⁢                          z              6                                +                      40            ⁢                          z              5                                +                      ABz            4                    +                      60            ⁢                          z              3                                +                      A4z            2                    +                      7            ⁢            Fz                    +          46                                                  L          ⁡                      (            Z            )                          =                                                                           ⁢          z                                                  M          ⁡                      (            Z            )                          =                              1            ⁢                          Dz              3                                +                      1            ⁢                          Cz              2                        ⁢                                                               +          1                    
After fourth Galois-field operations                               A          ⁡                      (            z            )                          =                                                                                                                                                                                                                          ⁢            79            ⁢                          z              2                                +                      10            ⁢            z                    +          96                                                  B          ⁡                      (            z            )                          =                                                                                          ⁢                          D1z              13                                +                      43            ⁢                          z              12                                +                      E9z            11                    +                      2            ⁢                          z              10                                +                      DCz            9                    +                      E4z            8                    +                      8            ⁢                          Ez              7                                +                      46            ⁢                          z              6                                +                      40            ⁢                          z              5                                +                      ABz            4                    +                      60            ⁢                          z              3                                +                      A4z            2                    +                      7            ⁢            Fz                    +          46                                                  L          ⁡                      (            Z            )                          =                  xe2x80x83                ⁢                              84            ⁢                          z              3                                +                      3            ⁢                          Cz              2                                +          z          +          B8                                                  M          ⁡                      (            Z            )                          =                              1            ⁢                          Dz              3                                +                      1            ⁢                          Cz              2                        ⁢                                                               +          1                    
Result
"sgr"(z)=L(Z)=84z3+3Cz2+z+B8
A third example of operations in the Euclid""s algorithm in the prior example is described in the following. This example of operations is in the case where S15= . . . =sn=0 and snxe2x88x921xe2x89xa00, where nxe2x89xa615, and n is an integer, for the coefficients of the syndrome equation S(z). In this example of operations, after fourth operations on the Galois field, the error-locator-polynomial "sgr"(z) is obtained.
Third example of operations in prior Euclidean algorithm. Syndrome.
S(z)=FEz13+D8z12+9Fz11+D8z10+09z9+9Dz8+E 7z7+B7z6+91z5+0Bz4+6Bz3+79z2+FDz+90
After initial setting                               A          ⁡                      (            z            )                          =                  z          16                                                  B          ⁡                      (            z            )                          =                                                                                           ⁢                          FEz              13                                +                      D8z            12                    +                      9            ⁢                          Fz              11                                +                      D8z            10                    +                      09            ⁢                          z              9                                +                      9            ⁢                          Dz              8                                +                      E7z            7                    +                      B7z            6                    +                      91            ⁢                          z              5                                +                      0            ⁢                          Bz              4                                +                      6            ⁢                          Bz              3                                +                      79            ⁢                          z              2                                +          FDz          +          90                                                  L          ⁡                      (            Z            )                          =                                                                               ⁢          0                                                  M          ⁡                      (            Z            )                          =                                                                              ⁢          1                    
After first Galois-field operations                               A          ⁡                      (            z            )                          =                              D8z            15                    +                      9            ⁢                          Fz              14                                +                      D8z            13                    +                      09            ⁢                          z              12                                +                      9            ⁢                          Dz              11                                +                      E7z            10                    +                      B7z            9                    +                      91            ⁢                          z              8                                +                      0            ⁢                          Bz              7                                +                      6            ⁢                          Bz              6                                +                      79            ⁢                          z              5                                +                      FDz            4                    +                      90            ⁢                          z              3                                                                        B          ⁡                      (            z            )                          =                                                                                           ⁢                          FEz              13                                +                      D8z            12                    +                      9            ⁢                          Fz              11                                +                      D8z            10                    +                      09            ⁢                          z              9                                +                      9            ⁢                          Dz              8                                +                      E7z            7                    +                      B7z            6                    +                      91            ⁢                          z              5                                +                      0            ⁢                          Bz              4                                +                      6            ⁢                          Bz              3                                +                      79            ⁢                          z              2                                +          FDz          +          90                                                  L          ⁡                      (            Z            )                          =                  xe2x80x83                ⁢                  z          3                                                  M          ⁡                      (            Z            )                          =                                                                              ⁢          1                    
After second Galois-field operations                               A          ⁡                      (            z            )                          =                                                                               ⁢                          ECz              14                                +                      7            ⁢                          Az              13                                +                      7            ⁢                          Az              12                                +                      C1z            11                    +                      83            ⁢                          z              10                                +                      4            ⁢                          Dz              9                                +                      F0z            8                    +                      C1z            7                    +                      F1z            6                    +                      FAz            5                    +                      C6z            4                    +                      EDz            3                    +                      A9z            2                                                            B          ⁡                      (            z            )                          =                                                                                           ⁢                          FEz              13                                +                      D8z            12                    +                      9            ⁢                          Fz              11                                +                      D8z            10                    +                      9            ⁢                          z              9                                +                      9            ⁢                          Dz              8                                +                      E7z            7                    +                      B7z            6                    +                      91            ⁢                          z              5                                +                      Bz            4                    +                      6            ⁢                          Bz              3                                +                      79            ⁢                          z              2                                +          FDz          +          90                                                  L          ⁡                      (            Z            )                          =                  xe2x80x83                ⁢                              z            3                    +                      63            ⁢                          z              2                                                                        M          ⁡                      (            Z            )                          =                                                                              ⁢          1                    
After third Galois-field operations                               A          ⁡                      (            z            )                          =                                                                                           ⁢            1            ⁢                          Az              13                                +                      87            ⁢                          z              12                                +                      A1z            11                    +                      87            ⁢                          z              10                                +                      2            ⁢                          Cz              9                                +                      8            ⁢                          Cz              8                                +                      43            ⁢                          z              7                                +                      FFz            6                    +                      62            ⁢                          z              5                        ⁢                                                             +                      z            4                    +                      22            ⁢                          z              3                                +                      97            ⁢                          z              2                                +                      40            ⁢            z                                                            B          ⁡                      (            z            )                          =                                                                                           ⁢                          FEz              13                                +                      D8z            12                    +                      9            ⁢                          Fz              11                                +                      D8z            10                    +                      9            ⁢                          z              9                                +                      9            ⁢                          Dz              8                                +                      E7z            7                    +                      B7z            6                    +                      91            ⁢                          z              5                                +                      Bz            4                    +                      6            ⁢                          Bz              3                                +                      79            ⁢                          z              2                                +          FDz          +          90                                                  L          ⁡                      (            Z            )                          =                  xe2x80x83                ⁢                              z            3                    +                      63            ⁢                          z              2                                +                      4            ⁢            Ez                                                            M          ⁡                      (            Z            )                          =                                                                              ⁢          1                    
After fourth Galois-field operations                               A          ⁡                      (            z            )                          =                                                                                                                                                                                                                            ⁢                          EDz              2                                +          EFz          +          FA                                                  B          ⁡                      (            z            )                          =                                                                                           ⁢                          FEz              13                                +                      D8z            12                    +                      9            ⁢                          Fz              11                                +                      D8z            10                    +                      9            ⁢                          z              9                                +                      9            ⁢                          Dz              8                                +                      E7z            7                    +                      B7z            6                    +                      91            ⁢                          z              5                                +                      Bz            4                    +                      6            ⁢                          Bz              3                                +                      79            ⁢                          z              2                                +          FDz          +          90                                                  L          ⁡                      (            Z            )                          =                  xe2x80x83                ⁢                              z            3                    +                      63            ⁢                          z              2                                +                      4            ⁢            Ez                    +          98                                                  M          ⁡                      (            Z            )                          =                                                                              ⁢          1                    
Result
"sgr"(z)=L(Z)=z3+63z2+4Ez+98
As described above, in the prior Euclid""s algorithm, a great number of Galois-field operations are required, and this fact has been an obstacle to increase the speed of processing.
As described above, there has been a problem that the scale of hardware becomes large in order to accommodate high-speed processing in the prior Reed-Solomon error-correcting circuit. Also, a great number of Galois-field operations are required and become an obstacle to increase the speed of processing.